package sort

//冒泡排序
//特点: 两两比较，每次外循环结束，左侧已排序区多一个已排序元素
//时间O(N^2),空间O(1) 稳定
//说明：这个个仅仅是简单的两两交换，也就是第一个元素一直和后面的比较，并非相邻记录两两交换
func BubbleSortC(arr []int) {
	arrLen := len(arr)
	for i := 0; i < arrLen; i++ {
		for j := i + 1; j < arrLen; j++ {
			if arr[i] >= arr[j] {
				//两两交换
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
}

//正宗的冒泡排序
//相邻记录两两比较，如果反序则交换
func BubbleSort(arr []int) {
	l := len(arr)
	flag := true //正宗的冒泡可以优化的
	for i := 0; i < l && flag; i++ {
		flag = false
		for j := l - 2; j >= i; j-- { //区别1:从序列后面开始
			if arr[j] > arr[j+1] { //区别2:比较的是j和j-1
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = true
			}
		}
	}
}
